#include<vector>
using namespace std;
//34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return { -1,-1 };
        }
        int end = lower_bound(nums, target + 1) - 1;
        return{ start,end };
    }
};

//35. 搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }
};


//704. 二分查找
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int left=0,right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target){
                right=mid-1;
            }else{
                left=mid+1;
            }
            
        }
        if(left<nums.size()&&nums[left]==target)
        return left;
        else 
        return -1;
        

    }
    
};

//744. 寻找比目标字母大的最小字母
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left=0,right=(int)letters.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(letters[mid]>target){//这里>=不行
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        if(left<letters.size()&&letters[left]>=target)//可改
        return letters[left];
        else
        return letters[0];
    }
};

//2529. 正整数和负整数的最大计数
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int neg=0,pos=0;
        for(int x:nums){
            if(x<0){
                neg++;
            }else if(x>0){
                pos++;
            }
        }
        return max(neg,pos);
    }
};

// 1385. 两个数组间的距离值
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int n1=arr1.size(),n2=arr2.size();
        int cnt=0;
        for(int i=0;i<n1;i++){
            int cn=0;
            for(int j=0;j<n2;j++){
                if(abs(arr1[i]-arr2[j])<=d)
                break;
                else
                cn++;
            }
            if(cn==n2)
            cnt++;
        }
        return cnt;
    }
};

//2300. 咒语和药水的成功对数

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        ranges::sort(potions);//C++20新特性
        for(int &x:spells)//x是spell中每个元素的引用，不是副本
        {
            long long target=(success-1)/x;//不等式变形
            if(target<potions.back()){//back是获取potion中最大元素
                x=potions.end()-ranges::upper_bound(potions,(int)target);
            }else{
                x=0;
            }
        }
        return spells;
    }
};

//2389. 和有限的最长子序列
/*class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        int n=nums.size(),m=queries.size();
        sort(nums.begin(),nums.end());
        vector<int>f(n+1);
        for(int i=0;i<n;i++){
            f[i+1]=f[i]+nums[i];
        }
        vector<int>answer(m);
        for(int i=0;i<m;i++){
            answer[i]=upper_bound(f.begin(),f.end(),queries[i])-f.begin()-1;
            //由于 upper_bound 返回的是第一个大于查询值的位置，而我们需要的是不大于查询值的最大前缀和的位置，因此从返回的位置减去 1。
        }
        return answer;
    }
};*/
class Solution{
public:
     vector<int> answerQueries(vector<int>& nums, vector<int>& queries){
        ranges::sort(nums);//排序
        //原地求和
        partial_sum(nums.begin(),nums.end(),nums.begin());
        for(int&q:queries){
            q=ranges::upper_bound(nums,q)-nums.begin();
        }
        return queries;

     }
};

//2080. 区间内查询数字的频率
class RangeFreqQuery {
private:
    //下标数组为值,数值为键的哈希表
    unordered_map<int,vector<int>> occurence;

public:
    RangeFreqQuery(vector<int>& arr) {
        //顺序遍历数组初始化哈希表
        int n=arr.size();
        for(int i=0;i<n;i++){
            occurence[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        //查找对应的出现下标数组，不存在则为空
        const vector<int>& pos=occurence[value];
        //二分查找寻找到数组中第一个大于等于 left 的位置 l 与第一个大于 right 的位置r
        auto l=lower_bound(pos.begin(),pos.end(),left);
        auto r=upper_bound(pos.begin(),pos.end(),right);
        return r-l;
    }
};

//2563. 统计公平数对的数目
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        ranges::sort(nums);
        long long ans=0;
        for(int j=0;j<nums.size();j++){
            auto r=upper_bound(nums.begin(),nums.begin()+j,upper-nums[j]);
            auto l=lower_bound(nums.begin(),nums.begin()+j,lower-nums[j]);
            ans+=r-l;
        }
        return ans;
    }
};


//981. 基于时间的键值存储
class TimeMap {
    unordered_map<string,vector<pair<int,string>>> m;
public:
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        m[key].emplace_back(timestamp,value);
    }
    
    string get(string key, int timestamp) {
        auto &pairs=m[key];//auto 会依据 m[key] 的返回值类型来推导 pairs 的类型。
        pair<int,string> p={timestamp,string({127})};
        auto i=upper_bound(pairs.begin(),pairs.end(),p);
        if(i!=pairs.begin()){//存在小于timestamp的值
            return(i-1)->second;//哈希的第二个值
        }
        return "";
    }
};


//1146. 快照数组
class SnapshotArray {
    unordered_map<int,vector<pair<int,int>>> history;
    int cur_snap_id=0;

public:
    SnapshotArray(int length) {
        
    }
    
    void set(int index, int val) {
        history[index].emplace_back(cur_snap_id,val);
    }
    
    int snap() {
        return cur_snap_id++;
    }
    
    int get(int index, int snap_id) {
        auto& h=history[index];
        int j=ranges::lower_bound(h,pair(snap_id+1,0))-h.begin()-1;
         //0 在这里只是一个占位值，其作用是让 std::pair 能够正确构造
         //pair(snap_id + 1, 0) 是要查找的目标值，这里使用 snap_id + 1 是为了找到第一个大于 snap_id 的快照编号。
        return j>=0 ? h[j].second : 0;
       
    }
};


//658. 找到 K 个最接近的元素
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int right=lower_bound(arr.begin(),arr.end(),x)-arr.begin();
        int left=right-1;
        while(k--){
            if(left<0){
                right++;//意味着已经到了数组的左边界，此时只能向右扩展
            }else if(right>=arr.size()){
                left--;//同上理由
            }else if(x-arr[left]<=arr[right]-x){
                left--;//意味着已经到了数组的左边界，此时只能向右扩展
            }else{
                right++;
            }
        }
        return vector<int>(arr.begin()+left+1,arr.begin()+right);//vector<int>(first, last) 采用左闭右开区间 [first, last)
    }
};


//911. 在线选举
class TopVotedCandidate {
public:
    vector<int> tops;
    vector<int> times;

    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        unordered_map<int,int>voteCounts;
        voteCounts[-1]=-1;
        int top=-1;
        for(auto& p:persons){
            voteCounts[p]++;
            if(voteCounts[p]>=voteCounts[top]){
                top=p;
            }
            tops.emplace_back(top);

        }
        this->times=times;
    }
    
    int q(int t) {
        int pos=upper_bound(times.begin(),times.end(),t)-times.begin()-1;
        return tops[pos];
    }
};


//LCP 08. 剧情触发时间
class Solution {
public:
    vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
        int len1=increase.size(),len2=requirements.size();
        vector<int>A(len2,-1);//长度len2,大小初始-1
        for(int i=1;i<len1;i++){
            increase[i][0]+=increase[i-1][0];
            increase[i][1]+=increase[i-1][1];
            increase[i][2]+=increase[i-1][2];
        }
        for(int i=0;i<len2;i++)
        {
            int left=0,right=len1-1,mid;
            int r0=requirements[i][0],r1=requirements[i][1],r2=requirements[i][2];
            if(r0==0&&r1==0&&r2==0){
                A[i]=0;
                continue;
            }
            while(left<=right)
            {
                mid=left+(right-left)/2;
                if(increase[mid][0]>=r0&&increase[mid][1]>=r1&&increase[mid][2]>=r2)
                right=mid-1;
                else
                left=mid+1;
            }
            if(left<len1)//当 left < len1 时，这表明在 increase 数组里找到了满足需求的元素。要是 left 等于 len1，那就意味着在 increase 数组中没有找到满足需求的元素
            A[i]=left+1;//时间点从 1 开始计数
        }
        return A;
    }
};
